﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmExamples.字符串类算法
{
    public class FindShortestSubstringContainingTarget
    {
        public FindShortestSubstringContainingTarget(string source,string target)
        {
            string result = GetShortestSubstringContainingTarget(source, target);
            Console.WriteLine(result);  // Output: "banc"
        }

        private string GetShortestSubstringContainingTarget(string source, string target)
        {
            if (string.IsNullOrEmpty(source) || string.IsNullOrEmpty(target))
                return string.Empty;

            Dictionary<char, int> targetCount = new Dictionary<char, int>();
            foreach (char c in target)
            {
                targetCount[c] = 0;
            }
            foreach (char c in target)
            {
                targetCount[c]++;
            }

            int left = 0, right = 0;
            int minStart = 0, minLength = int.MaxValue;
            int matched = 0;
            Dictionary<char, int> windowCount = new Dictionary<char, int>();

            while (right < source.Length)
            {
                char rightChar = source[right];

                if (targetCount.ContainsKey(rightChar))
                {
                    if (!windowCount.ContainsKey(rightChar))
                        windowCount[rightChar] = 0;
                    windowCount[rightChar]++;

                    if (windowCount[rightChar] == targetCount[rightChar])
                        matched++;
                }

                while (matched == targetCount.Count)
                {
                    if (right - left + 1 < minLength)
                    {
                        minStart = left;
                        minLength = right - left + 1;
                    }

                    char leftChar = source[left];

                    if (targetCount.ContainsKey(leftChar))
                    {
                        windowCount[leftChar]--;

                        if (windowCount[leftChar] < targetCount[leftChar])
                            matched--;
                    }

                    left++;
                }

                right++;
            }

            return minLength == int.MaxValue ? string.Empty : source.Substring(minStart, minLength);
        }
    }
}
